import numpy as np

def ant_colony_optimization(values, weights, max_weight, colony_size=10, max_iter=100, pheromone_evaporation=0.5, alpha=1, beta=2):
    num_items = len(values)
    pheromones = np.ones(num_items)  # 初始化信息素矩阵

    best_solution = None
    best_value = 0

    for iteration in range(max_iter):
        solutions = []

        for ant in range(colony_size):
            solution = construct_solution(pheromones, values, weights, max_weight, alpha, beta)
            total_value = calculate_total_value(solution, values)
            solutions.append((solution, total_value))

            if total_value > best_value:
                best_solution = solution
                best_value = total_value

        update_pheromones(pheromones, solutions, evaporation_rate=pheromone_evaporation)

    return best_solution, best_value

def construct_solution(pheromones, values, weights, max_weight, alpha, beta):
    num_items = len(values)
    remaining_items = list(range(num_items))
    solution = np.zeros(num_items)
    total_weight = 0

    while remaining_items:
        probabilities = calculate_probabilities(pheromones, values, weights, max_weight, remaining_items, alpha, beta)
        selected_item = np.random.choice(remaining_items, p=probabilities)
        remaining_items.remove(selected_item)
        new_weight = total_weight + weights[selected_item]

        if new_weight <= max_weight:
            solution[selected_item] = 1
            total_weight = new_weight
        else:
            break

    return solution

def calculate_probabilities(pheromones, values, weights, max_weight, remaining_items, alpha, beta):
    num_remaining = len(remaining_items)
    probabilities = np.zeros(num_remaining)

    for i, item in enumerate(remaining_items):
        probabilities[i] = (pheromones[item] ** alpha) * ((values[item] / weights[item]) ** beta)

    total_probability = np.sum(probabilities)
    if total_probability == 0:
        return np.ones(num_remaining) / num_remaining
    else:
        return probabilities / total_probability

def calculate_total_value(solution, values):
    return np.sum(solution * values)

def update_pheromones(pheromones, solutions, evaporation_rate):
    pheromones *= (1 - evaporation_rate)  # 信息素蒸发

    for solution, total_value in solutions:
        pheromones += solution / total_value  # 信息素增强

# 示例输入数据
values = np.array([10, 40, 30, 50])
weights = np.array([5, 4, 6, 3])
max_weight = 10

# 调用蚁群算法解决01背包问题
best_solution, best_value = ant_colony_optimization(values, weights, max_weight)

# 输出结果
print("Best Solution:", best_solution)
print("Best Value:", best_value)